//
//  SolveNQueens.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/24.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  51. N皇后 困难

/*
 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

 https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/8-queens.png
 上图为 8 皇后问题的一种解法。

 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 示例:

 输入: 4
 输出: [
  [".Q..",  // 解法 1
   "...Q",
   "Q...",
   "..Q."],

  ["..Q.",  // 解法 2
   "Q...",
   "...Q",
   ".Q.."]
 ]
 解释: 4 皇后问题存在两个不同的解法。
  

 提示：

 皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/n-queens
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 */

import UIKit

class SolveNQueens: NSObject {
    
    var resultArr:[[[String]]] = []
    
    func solveNQueens(_ n: Int) -> [[String]] {
        
        //创建一个NxN的棋盘 空格用E表示，皇后落位标记为Q，落位后换后可攻击的各自全部置为A 然后进行回溯算法
        
        var checkerBoard:[[String]] = []
        
        for _ in 0 ..< n{
            var boradArr:[String] = []
            for _ in 0 ..< n{
                boradArr.append("E")
            }
            checkerBoard.append(boradArr)
        }
        
        //print("棋盘：\(checkerBoard)")
        //print(self.setAtteckPoint([0,0], checkerBoard))
        
        //self.logBoard(checkerBoard)
        //print("假设皇后在2，2落位")
        //self.logBoard(self.setAtteckPoint([2,2], checkerBoard))
        
        self.dfs(n, 0, [], checkerBoard)
        
        
        var backResult:[[String]] = []

        for index1 in 0 ..< resultArr.count{
            backResult.append([])
            for index2 in 0 ..< n {
                backResult[index1].append("")
                var backString = ""
                for index3 in 0 ..< n {
                    if resultArr[index1][index2][index3] == "A" || resultArr[index1][index2][index3] == "E" {
                        resultArr[index1][index2][index3] = "."
                    }

                }
                backString = resultArr[index1][index2].joined(separator: "")

                backResult[index1][index2] = backString
            }
        }
        
//        print("\(backResult)")
        
        for arr in resultArr{
            self.logBoard(arr)
        }
//        print(resultArr)
        
        return backResult
    }
    
    func dfs(_ queensNum:Int, _ currentQueenNum:Int, _ tmpArr:[[Int]], _ sourceKeyBorad:[[String]]){
        
        var arr = tmpArr
        //var queensNum = queensNum
        
        if arr.count == queensNum{
            //self.logBoard(sourceKeyBorad)
            self.resultArr.append(sourceKeyBorad)
            return
        }
        
//        if arr.count != currentQueenNum {
//            return
//        }
        
        let sourceKeyBorad = sourceKeyBorad

        //寻找第一个可以落位的点
        for num2 in 0 ..< queensNum {

            //print("皇后\(currentQueenNum)在查询\(currentQueenNum),\(num2)是否可以落位落位")
            if self.validPoint([currentQueenNum,num2], sourceKeyBorad) {
                //皇后落位
                arr.append([currentQueenNum,num2])
                //print("皇后\(currentQueenNum)在\(currentQueenNum),\(num2)落位")
                //设置棋盘
                var setedBoard = self.setAtteckPoint([currentQueenNum,num2], sourceKeyBorad)
                //回溯
                self.dfs(queensNum, currentQueenNum + 1, arr, setedBoard)
                //减枝
                //print("皇后\(currentQueenNum)在\(currentQueenNum),\(num2)减枝")
                arr.removeLast()
                //减枝后棋盘也要恢复
                setedBoard = sourceKeyBorad
                
            }else{

                //print("皇后\(currentQueenNum)查询到\(currentQueenNum),\(num2)不可落位")
                if num2 == queensNum - 1 {
                    //无结果 减枝
                    //print("皇后\(currentQueenNum)本次没有在指定行找到自己的位置")
                    return
                }
            }
        }
    }
    
    //某点是否可以落位
    func validPoint(_ point:[Int], _ checkerBoard:[[String]])-> Bool{

        return checkerBoard[point[0]][point[1]] == "E"
    }
    
    //皇后落位后 将其可以攻击的点置为A
    func setAtteckPoint(_ queenPoint:[Int], _ originalBoard:[[String]])-> [[String]]{
        var originalBoard = originalBoard
        let count = originalBoard.count
        //横
        for index in 0 ..< count{
            if index == queenPoint[1] || originalBoard[queenPoint[0]][index] == "A" {
                continue
            }
            originalBoard[queenPoint[0]][index] = "A"
        }
        
        //纵
        for index in 0 ..< count{
            if index == queenPoint[0] || originalBoard[index][queenPoint[1]] == "A"{
                continue
            }
            originalBoard[index][queenPoint[1]] = "A"
        }
        
        //斜 四个方向分别计算
        //    \/
        //    /\
        //左上 ↖
        var tmpPoint1 = queenPoint
        for _ in 0 ..< count{
            if tmpPoint1[0]-1 >= 0 && tmpPoint1[1]-1 >= 0 {
                if originalBoard[tmpPoint1[0]-1][tmpPoint1[1]-1] != "A" {
                    originalBoard[tmpPoint1[0]-1][tmpPoint1[1]-1] = "A"
                }
                tmpPoint1[0] = tmpPoint1[0] - 1
                tmpPoint1[1] = tmpPoint1[1] - 1
            }else{
                break
            }
        }

        //右下 ↘
        var tmpPoint2 = queenPoint
        for _ in 0 ..< count{
            if tmpPoint2[0]+1 < count && tmpPoint2[1]+1 < count {
                if originalBoard[tmpPoint2[0]+1][tmpPoint2[1]+1] != "A" {
                    originalBoard[tmpPoint2[0]+1][tmpPoint2[1]+1] = "A"
                }
                tmpPoint2[0] = tmpPoint2[0] + 1
                tmpPoint2[1] = tmpPoint2[1] + 1
            }else{
                break
            }
        }
        
        //右上 ↗
        var tmpPoint3 = queenPoint
        for _ in 0 ..< count{
            if tmpPoint3[0]-1 >= 0 && tmpPoint3[1]+1 < count {
                if originalBoard[tmpPoint3[0]-1][tmpPoint3[1]+1] != "A" {
                    originalBoard[tmpPoint3[0]-1][tmpPoint3[1]+1] = "A"
                    
                }
                tmpPoint3[0] = tmpPoint3[0] - 1
                tmpPoint3[1] = tmpPoint3[1] + 1
            }else{
                break
            }
        }
        //左下 ↙
        var tmpPoint4 = queenPoint
        for _ in 0 ..< count{
            if tmpPoint4[0]+1 < count && tmpPoint4[1]-1 >= 0 {
                if originalBoard[tmpPoint4[0]+1][tmpPoint4[1]-1] != "A" {
                    originalBoard[tmpPoint4[0]+1][tmpPoint4[1]-1] = "A"
                    
                }
                tmpPoint4[0] = tmpPoint4[0] + 1
                tmpPoint4[1] = tmpPoint4[1] - 1
            }else{
                break
            }
        }

        //皇后落位
        originalBoard[queenPoint[0]][queenPoint[1]] = "Q"
        
        return originalBoard
    }
    
    //打印棋盘
    func logBoard(_ borad:[[String]]){
        for arr in borad{
            print("\(arr)\n")
        }

        print("********************")
    }
    
}
